Vol.80 MI Lecture Notes|九州大学 マス・フォア・インダストリ研究所 math 5acd77b7a56ce

MI Lecture Note Vol.80 : Kyushu University

ISSN2188−1200

九州大学マス・フォア・インダストリ研究所

九州大学マス・フォア・インダストリ研究所

九州大学大学院 数理学府

URL http://www.imi.kyushu-u.ac.jp/

M

IMI Workshop of the Joint Research Projects

Cryptographic Technologies for Securing Network Storage

and Their Mathematical Modeling

IMI Workshop of the Joint Research Projects

Cryptographic Technologies for Securing Network Storage

and Their Mathematical Modeling

Editors: Kirill Morozov, Hiroaki Anada, Yuji Suga

About MI Lecture Note Series

The Math-for-Industry (MI) Lecture Note Series is the successor to the COE Lecture

Notes, which were published for the 21st COE Program “Development of Dynamic

Mathematics with High Functionality,” sponsored by Japan’s Ministry of Education,

Culture, Sports, Science and Technology (MEXT) from 2003 to 2007. The MI

Lec-ture Note Series has published the notes of lecLec-tures organized under the following two

programs: “Training Program for Ph.D. and New Master’s Degree in Mathematics as

Required by Industry,” adopted as a Support Program for Improving Graduate School

Education by MEXT from 2007 to 2009; and “Education-and-Research Hub for

Mathematics-for-Industry,” adopted as a Global COE Program by MEXT from 2008 to

2012.

In accordance with the establishment of the Institute of Mathematics for Industry (IMI)

in April 2011 and the authorization of IMI’s Joint Research Center for Advanced and

Fundamental Mathematics-for-Industry as a MEXT Joint Usage / Research Center in

April 2013, hereafter the MI Lecture Notes Series will publish lecture notes and

pro-ceedings by worldwide researchers of MI to contribute to the development of MI.

October 2014

Yasuhide Fukumoto

Director

Institute of Mathematics for Industry

IMI Workshop of the Joint Research Projects

Cryptographic Technologies for Securing Network Storage

and Their Mathematical Modeling

MI Lecture Note Vol.80, Institute of Mathematics for Industry, Kyushu University ISSN 2188-1200

Date of issue: March 30, 2018

Editors: Kirill Morozov, Hiroaki Anada, Yuji Suga Publisher:

Institute of Mathematics for Industry, Kyushu University Graduate School of Mathematics, Kyushu University Motooka 744, Nishi-ku, Fukuoka, 819-0395, JAPAN Tel +81-(0)92-802-4402, Fax +81-(0)92-802-4405 URL http://www.imi.kyushu-u.ac.jp/

Printed by

Kijima Printing, Inc.

Shirogane 2-9-6, Chuo-ku, Fukuoka, 810-0012, Japan TEL +81-(0)92-531-7102 FAX +81-(0)92-524-4411

IMI Workshop of the Joint Research Projects

Workshop on Cryptographic Technologies

for Securing Network Storage

and Their Mathematical Modeling

June 12

th

– 13

th

_{, 2017}

Industry-University-Government Collaboration Innovation Plaza

3-8-34 Momochihama Sawara-ku Fukuoka 814-0001, Japan

Sponsored by

Institute of Mathematics for Industry (IMI),

Kyushu University

Organized by

Kirill Morozov, Hiroaki Anada, and Yuji Suga

Acknowledgements

One of the organizers, Kirill Morozov, was partially supported by a

kakenhi

Grant-in-Aid for Scientific Research (C) 15K00186 from Japan Society for

the Promotion of Science concerning his invitation of Prof. Beimel and

Prof. Desmedt, as well as his own participation to this workshop.

One of the organizers, Hiroaki Anada, was partially supported by a kakenhi

Grant-in-Aid for Scientific Research (C) 15K00029 from Japan Society

for the Promotion of Science concerning his invitation of Prof. Kushilevitz

to this workshop.

Preface

Rapid development of computer systems and networks emphasized importance of application of cryptographic technologies. Confidentiality and reliability can be naturally attained using the cryptographic technology of secret-sharing, which has been more and more widely applied for secure storage. However, data must not only be securely stored but also securely processed, and therefore search and computation over secured data becomes an increasingly important problem that finds applications

in digital payment systems, medical data processing, and other important areas – these functionalities are

achieved using secure multi-party computation technologies. Acceptance of these concepts for practical deployment requires a thorough security evaluation, involving mathematical modeling of the implemented systems as well as their rigorous security proofs. The purpose of this workshop was to discuss the above aspects. The program included 3 keynote lectures, 6 invited lectures and a panel discussion, gathering over 40 attendees in total. The goal of these lecture notes is to raise awareness about the topics and results discussed at the workshop, especially among researchers in mathematics and developers in cloud computing and cybersecurity.

Kirill Morozov, Representative of the Organizers

Table 1. List of attendees.

Hiroaki Anada Tushar Kanti Saha Shinichi Matsumoto Nobuyuki Sugio Amos Beimel Ryo Kikuchi Tomoko Matsushima Yasushi Takahashi Bernardo David Dong-In Kim Toshiyasu Matsushima Tadanori Teruya Yvo Desmedt Eitaro Kohno Shota Nakasato Junting Xiao Tsumbuukhuu Dulguun Takeshi Koshiba Naohisa Nishida Masato Yamanouchi Goichiro Hanaoka Noboru Kunihiro Koji Nuida Masaya Yasuda Keisuke Hara Naruhiro Kurokawa Kazuma Ohara Kenji Yasunaga Masahiro Ishii Eyal Kushilevitz Kazuo Ohta Maki Yoshida Makoto Ishikawa Hyungu Lee Miyo Okada Yusuke Yoshida Mitsugu Iwamoto Shincheol Lee Eriko Osakabe Ye Yuan Hyungrok Jo Niklas Lemcke Yuji Suga Kirill Morozov

Photograph 1. Group photo in front of the venue.

六本松

Hashimoto

Nishijin Tenjin

Hakozaki

Hakata

Fukuoka Airport

JR K as_{hii L}

ine

JR K ag

osh_im a L

ine Nis

hite tsu Om

uta L ine

Ropponmatsu Meinohama

J R Other Line Subway Urban Expressway Nishikyushu Expressway ▶200 meters from

the Fukuoka Tower Industry-University-Government Collaboration Innovation Plaza

IMI Joint Research Project in 2017

Cryptographic Technologies

for Securing Network Storage

and Their Mathematical Modeling

Amos Beimel,

Ben-Gurion University

“Graph Secret Sharing”

Yvo Desmedt,

The University of Texas at Dallas

“Human Recomputable Secret Shares and their Applications in E-Voting”

Eyal Kushilevitz,

Technion

“Ad-hoc MPC”

Keynote speakers:

Bernardo David,

Tokyo Institute of Technology

Mitsugu Iwamoto,

The University of Electro-Communications

Ryo Kikuchi,

NIPPON TELEGRAPH AND TELEPHONE CORPORATION

Takeshi Koshiba,

Waseda University

Naruhiro Kurokawa,

Bank of Japan

Kazuma Ohara,

NEC Corporation

Invited speakers:

■Organizing Committee▶ ■

Hiroaki Anada

(University of Nagasaki) ■

Kirill Morozov

(Tokyo Institute of Technology) ■

Yuji Suga

(Internet Initiative Japan Inc.)

3-8-34 Momochihama Sawara-ku Fukuoka 814-0001, JAPAN https://airimaq.kyushu-u.ac.jp/en/airimaq/access.php

Venue:

AirIMaQ (Momochi), Seminar Room, 2F

Date:

June 12

(Mon)-

13

(Tue)

, 2017

http://www.imi.kyushu-u.ac.jp/eng/events/view/1240

(For general inquiries) Institute of Mathematics for Industry, Kyushu University TEL: 092-802-4402 E-mail: [email protected]

Contact

: [email protected]

■Sponsored by ▶ _{Institute of Mathematics for Industry, Kyushu University}

■Registration fee ▶ _Free

Industry-University-Government Collaboration Innovation Plaza

Program

June 12 (Monday)

10:00-10:10 (Opening)

[1] 10:10-10:50 [keynote] Amos Beimel, Ben-Gurion University, Israel

“Graph Secret Sharing”

[2] 11:10-11:50 [keynote] Yvo Desmedt, The University of Texas at Dallas, USA

“Human Recomputable Secret Shares and their Applications in E-Voting”

[3] 14:00-14:40

Mitsugu Iwamoto, The University of Electro-Communications, Japan

“Secret Sharing Schemes under Guessing Secrecy”

[4] 15:00-15:40

Naruhiro Kurokawa, Bank of Japan, Japan

“Function Secret Sharing Using Fourier Basis”

16:00-16:30 (Panel Discussion) Panelists: Bernardo David, Yvo Desmedt, Mitsugu Iwamoto,

Ryo Kikuchi, Naruhiro Kurokawa, Eyal Kushilevitz and Kazuma Ohara.

Moderator: Kirill Morozov

June 13 (Tuesday)

[5] 10:10-10:50 [keynote] Eyal Kushilevitz, Technion, Israel

“Ad-hoc MPC”

[6] 11:10-11:50

Takeshi Koshiba, Waseda University, Japan

“Secure Message Transmission against Rational Adversaries”

[7] 14:00-14:40

Kazuma Ohara, NEC Corporation, Japan

“Optimized Honest-Majority MPC for Malicious Adversaries

- Breaking the 1 Billion-Gate Per Second Barrier”

[8] 14:50-15:30

Ryo Kikuchi, NTT CORPORATION, Japan

“Key components in MEVAL”

[9] 15:40-16:20

Bernardo David, Tokyo Institute of Technology, Japan

“A Provably Secure Proof-of-Stake Blockchain Protocol”

16:20-16:30 (Closing)

Table of Contents

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Amos Beimel (Ben-Gurion University, Israel)

Joint work with Oriol Farr s, Yuval Mintz, and Naty Peter

Human Recomputable Secret Shares and their Applications in E-Voting

Yvo Desmedt (The University of Texas at Dallas, USA)

Secret Sharing Schemes Under Guessing Secrecy

Mitsugu Iwamoto (The University of Electro-Communications, Japan)

Joint work with Junji Shikata

Function Secret Sharing Using Fourier Basis

Naruhiro Kurokawa (Bank of Japan, Japan)

Joint work with Takuya Ohsawa and Takeshi Koshiba

Ad Hoc PSM Protocols: Secure Computation Without Coordination

Eyal Kushilevitz (Technion, Israel)

Joint work with Amos Beimel and Yuval Ishai

Secure Message Transmission against Rational Adversaries

Takeshi Koshiba (Waseda University, Japan)

Joint work with Maiki Fujita

Optimized Honest-Majority MPC for Malicious Adversaries

- Breaking the 1 Billion-Gate Per Second Barrier

Kazuma Ohara (NEC Corporation, Japan)

Joint work with Toshinori Araki, Assi Barak, Jun Furukawa, Yehuda Lindell, Ariel Nof, Adi Watzman, Or Weinstein

Key components in MEVAL

Ryo Kikuchi (NTT Corporation, Japan)

Joint work with Dai Ikarashi, Koki Hamada, Koji Chida, Naoto Kiribuchi, Gembu Morohashi

Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

Bernardo David (Tokyo Institute of Technology, Japan)

Joint work with Aggelos Kiayias, Alexander Russell and Roman Oliynykov

Panel Discussion: Cryptographic Technologies for Securing Network Storage

and Their Mathematical Modeling

à

　　・・・・・・・・・・　

1

　　・・・・・・・・・　

10

　　・・・・・・・・・・・・・・・・・・　

25

　　・・・・・・・・・・・・・・・・・・・・　

38

　　・・・・・・・・・・　

48

　　・・・・・・・・・・・・・・　

56

　　・・・・・・・・・・・・・・・・・・　

72

　　・・・・・・・・・・・・・・・・・・・・・・・・・・・　

86

　　・・・・・・・・・・　

100

　　・・・・・・・・・・・・・・・・・・・・・・・・　

116

IMI Workshop: Cryptographic Technologies for Securing Network Storage and Their Mathematical Modeling

June 12–13, 2017, Kyushu University

Linear Secret-Sharing Schemes for Forbidden

Graph Access Structures

Amos Beimel (Joint work with Oriol Farr`

as, Yuval Mintz, and

Naty Peter)

Ben Gurion University of the Negev

[email protected]

A secret-sharing scheme realizes the forbidden graph access structure determined by

a graph

G

= (

V, E

) if a pair of vertices can reconstruct the secret if and only if it is

and edge of

G

. An important property of these schemes is that they can be used to

construct schemes for the conditional disclosure of secrets.

We study the complexity of realizing a forbidden graph access structure by linear

secret-sharing schemes. A secret-sharing is linear if the reconstruction of the secret from

the shares is a linear mapping. In many applications of secret sharing, it is required

that the scheme is linear. We provide efficient constructions and lower bounds on the

share size of linear secret-sharing schemes for sparse and dense graphs, closing the gap

between upper and lower bounds: Given a sparse graph with

n

vertices and at most

n

1+β

_{edges, for some 0}

_≤

_{β <}

_{1, we construct a linear secret-sharing scheme realizing}

the forbidden graph access structure in which the total size of the shares is ˜

O

(

n

1+β/2

_).

We provide an additional construction showing that every dense graph with

n

vertices

and at least

(

n₂

)

−

n

1+β

_{edges can be realized by a linear secret-sharing scheme with}

the same share size.

We prove lower bounds on the share size of linear secret-sharing schemes realizing

forbidden graph access structures. We prove that for most forbidden graphs access

structures, the total share size of every linear secret-sharing scheme realizing the graph

is Ω(

n

3/2

_{), this shows that construction of [Gay, Kerenidis, and Wee, CRYPTO 2015]}

is optimal. Furthermore, we show that for every 0

< β

_≤

1 there exist a graph with at

most

n

1+β

_{edges and a graph with at least}

(

n

2

)

−

n

1+β

_{edges, such that the total share size}

of every linear secret-sharing scheme realizing these forbidden graph access structures

is Ω(

n

1+β/2

_{). This shows that our constructions are optimal (up to poly-logarithmic}

factors).

3742

Secret Sharing

3

6634 _{3441 2538 1329}

3

Secret Sharing

[Shamir79,Blakley79,ItoSaitoNishizeki87]

•Parties:      

•Access Structure   _{(collection of sets of parties)}

•A scheme realizes  if:

–Correctness: every authorized set   can recover s

–Privacy: every unauthorized set   cannot learn anything about 

4

P1 P2 Pn

Dealer

s

s1



r

s2 sn

Secret Sharing

for Forbidden Graphs

Amos Beimel, Ben-Gurion University

Based on works with

Oriol Farras, Universitat Rovira i Virgili

Yuval Mintz, Naty Peter, Ben-Gurion University

Cryptographic Technologies for Securing Network Storage

June 12, 2017

1

3742

2538 3441 1329 6634

Secret Sharing

2

Secret Sharing

for Forbidden Graphs

Amos Beimel, Ben-Gurion University

Based on works with

Oriol Farras, Universitat Rovira i Virgili

Yuval Mintz, Naty Peter, Ben-Gurion University

Cryptographic Technologies for Securing Network Storage

June 12, 2017

1

3742

2538 3441 1329 6634

Secret Sharing

2

Shamir’s t-out-of-n Secret Sharing

•Access structure: = {  ⊆  ∶ || ≥  } •Scheme:

•Dealer chooses a random polynomial

   − −

– Share of :

s

5

•

Input: secret s∈  where  > is a prime

= () mod 

Linear Secret Sharing

•Input: secret  ∈ 

•Dealer chooses random elements , … , ∈ •Share :

•A vector over

•Each coordinate: a linear combination of and ,… , 

•Example 1: Shamir’s scheme:

• = () = + ⋅ + 2⋅ 2 + ⋯ + −⋅ − •Example 2:  ∈ 2

•Dealer chooses , 2∈ 2 •= (, ⊕ ) •= ( ⊕ ) •= (,  ⊕ ⊕ )

6

Shamir’s

t

-out-of-

n

Secret Sharing

5

•Access structure:           •Scheme:

•Input: secret

s

•Dealer chooses a random polynomial

     



  







   







–Share of



:

 

s

  where    is a prime



Linear Secret Sharing

6

•Input: secret  

•Dealer chooses random elements     



•Share :

•A vector over 

•Each coordinate: a linear combination of  and    

•Example 1:   

•Dealer chooses   



•   



•   



•     



•Example 2 – Shamir’s scheme:

•             

3742

Secret Sharing

3

6634 _{3441 2538 1329}

3

Secret Sharing

[Shamir79,Blakley79,ItoSaitoNishizeki87]

•Parties:      

•Access Structure   _{(collection of sets of parties)}

•A scheme realizes  if:

–Correctness: every authorized set   can recover s

–Privacy: every unauthorized set   cannot learn anything about 

4

P1 P2 Pn

Dealer

s

s1



r

s2 sn

A Scheme Realizing a Forbidden Graph

9

•    



• For every edge     , – Give a random bit  to  and  to 

•  can reconstruct the secret by performing xor on their shares.

• In addition, share  using a 3-out-of- secret-sharing scheme



• Total share size:         



  

 

 

Upper Bounds for Forbidden Graphs

10

• Every graph can be realized by a secret-sharing scheme with share size      _{ }

_

_{LiuVaikuntanathanWee17]}

_

• Every graph can be realized by a linear secret-sharing scheme with share size _

_

_{GayKerenidisWee15]}

_

• We consider linear secret sharing schemes

• Questions:

• If







contains few edges, can we realize it more efficiently?

• Few = _{. Goal: better than }_{ }_

_

• If  contains many edges, can we realize it more efficiently?

• Many = _{  }

_

_

_{Goal: better than }

_

• If  has an efficient scheme and we add and remove few edges, can we realize it efficiently?



Why Secret Sharing?

7

• Storing sensitive information – Robust key management

• Used in many secure protocols:

• multiparty computation

• threshold cryptography

• attribute-based encryption (ABE)

• access control

• oblivious transfer

• Most applications require linear secret-sharing schemes

• Most known schemes are linear

Schemes for Forbidden Graphs

[SunShieh97]

A scheme realizes a forbidden graph    



if:

• The parties are the set of vertices 



• The authorized sets are:

• The edges in 



• Every set of size at least 

• The unauthorized sets are:

• The non-edges

• A single party (vertex)

8

Why Secret Sharing?

7

• Storing sensitive information – Robust key management

• Used in many secure protocols:

• multiparty computation

• threshold cryptography

• attribute-based encryption (ABE)

• access control

• oblivious transfer

• Most applications require linear secret-sharing schemes

• Most known schemes are linear

Schemes for Forbidden Graphs

[SunShieh97]

A scheme realizes a forbidden graph    



if:

• The parties are the set of vertices 



• The authorized sets are:

• The edges in 



• Every set of size at least 

• The unauthorized sets are:

• The non-edges

• A single party (vertex)

8

Motivation

11

• Secret sharing for forbidden bipartite graphs are equivalent to conditional disclosure of secrets

• Used to construct symmetric private information retrieval and attribute based encryption

• Our goal: construct efficient linear secret-sharing schemes for specific families of forbidden graphs

• We want to understand if, for forbidden graphs, linear secret sharing requires shares of size _

_

• 



Conditional Disclosure of Secrets (CDS)

[GertnerIshaiKushilevitzMalkin98]

• Each party has a private input

• Both parties know a secret 



• Shared randomness 



• Referee knows  



• A condition:    _{  }_{  }

_

• Each party sends one message

• Correctness: If     , Ref learns 



• Security: If     , Ref learns nothing

Ref

Learnsiff         Alice Bob       

Motivation

11

• Secret sharing for forbidden bipartite graphs are equivalent to conditional disclosure of secrets

• Used to construct symmetric private information retrieval and attribute based encryption

• Our goal: construct efficient linear secret-sharing schemes for specific families of forbidden graphs

• We want to understand if, for forbidden graphs, linear secret sharing requires shares of size _

_

• 



Conditional Disclosure of Secrets (CDS)

[GertnerIshaiKushilevitzMalkin98]

• Each party has a private input

• Both parties know a secret 



• Shared randomness 



• Referee knows  



• A condition:   _{  }_{  }

_

• Each party sends one message

• Correctness: If     , Ref learns 



• Security: If     , Ref learns nothing

Ref

Learnsiff        

Alice Bob

  

 

 

A Scheme Realizing a Forbidden Graph

9

•    



• For every edge     , – Give a random bit  to  and  to 

•  can reconstruct the secret by performing xor on their shares.

• In addition, share  using a 3-out-of- secret-sharing scheme



• Total share size:                 

Upper Bounds for Forbidden Graphs

10

• Every graph can be realized by a secret-sharing scheme with share size      _{ }

_

_{LiuVaikuntanathanWee17]}

_

• Every graph can be realized by a linear secret-sharing scheme with share size _

_

_{GayKerenidisWee15]}

_

• We consider linear secret sharing schemes

• Questions:

• If







contains few edges, can we realize it more efficiently?

• Few = _{. Goal: better than }_{ }_

_

• If  contains many edges, can we realize it more efficiently?

• Many = _{  }

_

_

_{Goal: better than }

_

• If  has an efficient scheme and we add and remove few edges, can we realize it efficiently?



Main Result: Upper Bounds

Thm 1:

If a graph withvertices contains for some     

– either at most  _{edges or}

– at least 

   edges,

Then there is a linear secret-sharing scheme realizing the graphwith total share size _



Thm 2: If

–  can be realized with a scheme with total share size  – obtained from by removing and adding at most _edges. Then there is a linear secret-sharing scheme realizing with share size

  _.

15

Main Result: Lower Bounds

• Thm 3: There exists a graph with  vertices such that in any linear

secret-sharing scheme realizing it with a one-bit secret the size of the shares is _

• Conclusion 1: The construction of Gay et al. is optimal

• Conclusion 2: Gap between linear and non-linear schemes for forbidden graphs

• Thm 4: There exists a graph with  vertices and at most  _edges

such that in any linear secret-sharing scheme realizing it with a one-bit secret the size of the shares is _

– Same result for a graph with at least 

   edges

• Conclusion 3: Our constructions are optimal up to a poly-log factor.

16

CDS and Forbidden Bipartite Secret Sharing

• Bipartite Graph:      • Vertices:   

• Edges: Only between sets     

• Secret sharing for forbidden bipartite graph

• Every    can reconstruct  • Every      s.t.    

should not learn information about 

 

CDS and Forbidden Bipartite Secret Sharing

• Given a CDS define: •      

•            • To share a secret :

•     



    



•   can reconstruct iff     



iff    



Ref

Learnsiff    

   _{  } Alice Bob    _{  }     00 01 11 10 00 01 11 10

  can reconstruct iff    

CDS and Forbidden Bipartite Secret Sharing

• Bipartite Graph:      • Vertices:   

• Edges: Only between sets     

• Secret sharing for forbidden bipartite graph

• Every    can reconstruct  • Every      s.t.    

should not learn information about 

 

CDS and Forbidden Bipartite Secret Sharing

• Given a CDS define: •      

•            • To share a secret :

•     



    



•   can reconstruct iff     



iff    



Ref

Learnsiff    

   _{  } Alice Bob    _{  }     00 01 11 10 00 01 11 10

  can reconstruct iff    

A Scheme for a Graph with

_



_Edges

• Basic Construction: for a bipartite graph      

such that  is small and every vertex in  has degree at most 



• Share size      

• Second construction: for a bipartite      such that every vertex in  has degree at most 

– Share size   

• Third construction: for a bipartite graph       that has at most  _edges

– Share size _

• Final construction: for a graph     that has at most 

edges

–Share size _

  

17

Basic Construction

• If      isbipartite graph s.t. every vertex in  has degree at most 



• Then  has a linear secret-sharing with total share size is      



Example:   ,   

Every    has degree at most    The total share size is 





 18  

A Scheme for a Graph with

_



_Edges

• Basic Construction: for a bipartite graph      

such that  is small and every vertex in  has degree at most 



• Share size      

• Second construction: for a bipartite      such that every vertex in  has degree at most 

– Share size   

• Third construction: for a bipartite graph       that has at most  _edges

– Share size _

• Final construction: for a graph     that has at most 

edges

–Share size _

  

17

Basic Construction

• If      isbipartite graph s.t. every vertex in  has degree at most 



• Then  has a linear secret-sharing with total share size is      



Example:   ,   

Every    has degree at most    The total share size is 





 18  

Main Result: Upper Bounds

Thm 1:

If a graph withvertices contains for some     

– either at most  _{edges or}

– at least 

   edges,

Then there is a linear secret-sharing scheme realizing the graphwith total share size _



Thm 2: If

–  can be realized with a scheme with total share size  – obtained from by removing and adding at most _edges. Then there is a linear secret-sharing scheme realizing with share size

  _.

15

Main Result: Lower Bounds

• Thm 3: There exists a graph with  vertices such that in any linear

secret-sharing scheme realizing it with a one-bit secret the size of the shares is _

• Conclusion 1: The construction of Gay et al. is optimal

• Conclusion 2: Gap between linear and non-linear schemes for forbidden graphs

• Thm 4: There exists a graph with  vertices and at most  _edges

such that in any linear secret-sharing scheme realizing it with a one-bit secret the size of the shares is _

– Same result for a graph with at least 

   edges

• Conclusion 3: Our constructions are optimal up to a poly-log factor.

16

Bipartite with Few Edges

If      isbipartite with at most _edges

Then  has a linear secret-sharing with total share size is _



• In this talk: _

Scheme:

• Let         

•   



 

• Realize        

– Share size           

• Realize        

– Share size       _{      }_

• In the paper: Reduce degree in  steps

23













Conclusions

• Forbidden graph secret sharing is equivalent to CDS ⇨ SPIR, Atribute based encryption

• Every forbidden graph can be realized by a linear secret-sharing scheme with share size _

• We show that every forbidden graph with _{edges can be realized}

by a linear secret-sharing scheme with share size _ – Same result for with 

  edges

• There exists a forbidden graph such that in any linear secret-sharing scheme realizing it the share size is _

• There exists a forbidden graph with _{edges such that in any linear}

secret-sharing scheme realizing it the share size is _ • Open: graph access structures

24

A Scheme with share size

• If = , ,  is bipartite graph

• Then has a linear secret-sharing with total share size is(/₎

Scheme:

• Partitioninto sets, … ,  of size 

• Define= , ,  ∩ (×)

• Realize eachwith a scheme with total share size  

• The total share size is ( ⋅  )





 _  _

A Scheme with share size





 • If = , ,  is bipartite graph s.t.

– The degree of every  ∈ is at most • Then has a linear secret-sharing with

total share size is (/2₎

With different parameters :

• Randomly partition into:

, … , of size / 

• Define= , ,  ∩ (×)

– With high prob. the degree of every  ∈ in

is at most 

• Realize each with a scheme with total share size   + (/ ) ⋅  = ()

• The total share size is ( ⋅ )

22

A Scheme with share size

_



_

• If      isbipartite graph

• Then  has a linear secret-sharing with total share size is _

Scheme:

• Partition  into sets      of size  • Define        • Realize each  with a scheme with total

share size  

• The total share size is    



 21 











_







 _



A Scheme with share size

_



_

• If      isbipartite graph s.t.

– The degree of every   is at most 

• Then  has a linear secret-sharing with total share size is _

Scheme:

• Randomly partition  into sets

     of size   • Define       

– With high prob. the degree of every    in 

is at most 

• Realize each  with a scheme with total

share size         

• The total share size is    



 22 











With different parameters:

• Schemewith total share size

     

Schemes for Graphs

A scheme realizes a graph    



if:

• The parties are the set of vertices 



• The authorized sets are:

• The edges in 



• Every set that contains an edge

• The unauthorized sets are:

• The non-edges

• Every set that doesn’t contain an edge

• Every graph can be realized by a linear scheme with share size _{}

• Sparse graph: 

• _

25

Thanks!

26

Schemes for Graphs

A scheme realizes a graph    



if:

• The parties are the set of vertices 



• The authorized sets are:

• The edges in 



• Every set that contains an edge

• The unauthorized sets are:

• The non-edges

• Every set that doesn’t contain an edge

• Every graph can be realized by a linear scheme with share size _{}

• Sparse graph: 

• _

25

Thanks!

26

Bipartite with Few Edges

If      isbipartite with at most _edges

Then  has a linear secret-sharing with total share size is _



• In this talk: _

Scheme:

• Let         

•   



 

• Realize        

– Share size           

• Realize        

– Share size       _{      }_

• In the paper: Reduce degree in  steps

23













Conclusions

• Forbidden graph secret sharing is equivalent to CDS ⇨ SPIR, Atribute based encryption

• Every forbidden graph can be realized by a linear secret-sharing scheme with share size _

• We show that every forbidden graph with _{edges can be realized}

by a linear secret-sharing scheme with share size _ – Same result for with 

  edges

• There exists a forbidden graph such that in any linear secret-sharing scheme realizing it the share size is _

• There exists a forbidden graph with _{edges such that in any linear}

secret-sharing scheme realizing it the share size is _ • Open: graph access structures

24

IMI Workshop: Cryptographic Technologies for Securing Network Storage and Their Mathematical Modeling

June 12–13, 2017, Kyushu University

Human Recomputable Secret Shares

and their Applications in E-Voting

Yvo Desmedt

The University of Texas at Dallas

[email protected]

The classical approach of secret sharing is to consider the secret to be in a finite

field. Computers are used by the dealer to make shares, and computers are used to

reconstruct the secret. Since the invention of Visual Cryptography by Kafri and Keren

in 1987, many researchers have stepped away from these restrictions.

In 2007, Desmedt-Pieprzyk-Steinfeld-Wang considered secrets that belong to a

non-Abelian group, such as the symmetric group (i.e., permutations), to obtain secure

multiparty computation.

In this talk, we consider secret and shares that are permutations, wonder how good

humans can do computations with these and consider them in the context of e-voting,

but then e-voting secure against hacking of the voter’s computer.

•a joint paper with Stelios Erotokritou at SCN 2012.

•a joint paper with Stelios Erotokritou at Vote ID 2015.

Special thanks to Rene Peralta whose November 9, 2011 suggestion to considerZ10(+)as an Abelian subgroup ofS10, allowed us to make

a more user-friendly scheme.

c

�Yvo Desmedt 2

O

VERVIEW

1. Special Secret Sharing Schemes

2. Our setting: Post Snowden elections

3. A pioneering approach: Chaum’s Code Voting 4. Advantages/disadvantages of Code Voting

5. Our setting, assumptions and their impacts

6. The voting: passive adversary only 7. Some usability tests (SCN 2012)

8. High level description 9. Details: technical background

10. The mixing for the single-seat: Efficiency improvement

11. The mixing for the single-seat MIX-friendly case

c

�Yvo Desmedt 3

Human Recomputable Secret Shares and

their Applications in E-Voting

Yvo Desmedt

Univ. of Texas at Dallas, US

June 12, 2017

c

�Yvo Desmedt

Yvo Desmedt’s work on anonymity was partially supported by: the US NSF ANI-0087641. The work on voting was partially sponsored by the UK EPSRC EP/C538285/1, by BT as BT Chair of Information Security and partly done while being Invited Senior Research Scientist at RCIS (AIST, Japan).

A part of this research was done while Yvo Desmedt visited AT&T Shannon Research, Tsinghua University (while funded by the National Natural Science Foundation of China Grant 60553001, and the National Basic Research Program of China Grant 2007CB807900 and 2007CB807901).

Part of this presentation is based on:

•unpublished research with Rebecca Wright (with her permission),

•a joint paper with Josef Pieprzyk, Ron Steinfeld and Huaxiong Wang (Crypto 2007)

c

�Yvo Desmedt 1

Human Recomputable Secret Shares and

their Applications in E-Voting

Yvo Desmedt

Univ. of Texas at Dallas, US

June 12, 2017

c

�Yvo Desmedt

Yvo Desmedt’s work on anonymity was partially supported by: the US NSF ANI-0087641. The work on voting was partially sponsored by the UK EPSRC EP/C538285/1, by BT as BT Chair of Information Security and partly done while being Invited Senior Research Scientist at RCIS (AIST, Japan).

A part of this research was done while Yvo Desmedt visited AT&T Shannon Research, Tsinghua University (while funded by the National Natural Science Foundation of China Grant 60553001, and the National Basic Research Program of China Grant 2007CB807900 and 2007CB807901).

Part of this presentation is based on:

•unpublished research with Rebecca Wright (with her permission),

•a joint paper with Josef Pieprzyk, Ron Steinfeld and Huaxiong Wang (Crypto 2007)

c

�Yvo Desmedt 1

12. The mixing for the multi-seat election

13. The active case: An announcement

14. Variants 15. Conclusions

c

�Yvo Desmedt 4

1.

S

PECIAL

S

ECRET

S

HARING

S

CHEMES

The most known secret sharing scheme is Shamir’s secret sharing scheme (over 11,000 citations). His approach was to consider:

1.thesecret and sharesto be in afinite field,

2.to have the dealer use acomputertogenerate shares, and 3.to usecomputers to reconstruct the secret.

Since the invention of Visual Cryptography by Kafri and Keren in 1987, many researchers have stepped away from these restrictions (note that this was reinvented by Naor and Shamir in 1994 and that Kafri-Keren have 225 citations and Naor-Shamir have 2741).

Generalizing from finite field to Abelian Groups was initiated by

c

�Yvo Desmedt 5

12. The mixing for the multi-seat election

13. The active case: An announcement

14. Variants 15. Conclusions

c

�Yvo Desmedt 4

1.

S

PECIAL

S

ECRET

S

HARING

S

CHEMES

The most known secret sharing scheme is Shamir’s secret sharing scheme (over 11,000 citations). His approach was to consider:

1.thesecret and sharesto be in afinite field,

2.to have the dealer use acomputertogenerate shares, and 3.to usecomputers to reconstruct the secret.

Since the invention of Visual Cryptography by Kafri and Keren in 1987, many researchers have stepped away from these restrictions (note that this was reinvented by Naor and Shamir in 1994 and that Kafri-Keren have 225 citations and Naor-Shamir have 2741).

Generalizing from finite field to Abelian Groups was initiated by

c

�Yvo Desmedt 5

•a joint paper with Stelios Erotokritou at SCN 2012.

•a joint paper with Stelios Erotokritou at Vote ID 2015.

Special thanks to Rene Peralta whose November 9, 2011 suggestion to considerZ10(+)as an Abelian subgroup ofS10, allowed us to make

a more user-friendly scheme.

c

�Yvo Desmedt 2

O

VERVIEW

1. Special Secret Sharing Schemes

2. Our setting: Post Snowden elections

3. A pioneering approach: Chaum’s Code Voting

4. Advantages/disadvantages of Code Voting 5. Our setting, assumptions and their impacts

6. The voting: passive adversary only

7. Some usability tests (SCN 2012) 8. High level description

9. Details: technical background

10. The mixing for the single-seat: Efficiency improvement 11. The mixing for the single-seat MIX-friendly case

c

�Yvo Desmedt 3

3.

A

PIONEERING APPROACH

: C

HAUM

’

S

C

ODE

V

OTING

c

�Yvo Desmedt and Stelios Erotokritou 8

c

�Yvo Desmedt and Stelios Erotokritou 9

Desmedt-Frankel, published in 1994 (see also: Cramer-Fehr, Cramer-Fehr-Stam and the Cramer-Fehr-Ishai-Kushilevitz application to MPC).

After many years of research, in 2007 Desmedt-Pieprzyk-Steinfeld-Wang succeeded in making black-box “MPC” computations over non-Abelian groups. The motivation was purely theoretical. Today we will see an application of the situation in which:

the secret and shares belongs to a non-Abelian group, i.e.,Sn(or a subgroup ofSn, such asZn).

c

�Yvo Desmedt 6

2.

O

UR SETTING

: P

OST

S

NOWDEN ELECTIONS

Post Snowden: today most people understand that computers, laptops can be hacked and may have trapdoors, malware, etc.

Potential solutions:

•Halderman (2015) recommended to stop using Internet Voting.

•We believe we need to restart/encourage a line of research in which we wonder how to vote assuming that the device you use for voting

has been hacked.

Our model(high level): we assume we cannottrust:

•any single party,

•any single device, etc.

c

�Yvo Desmedt 7

Desmedt-Frankel, published in 1994 (see also: Cramer-Fehr, Cramer-Fehr-Stam and the Cramer-Fehr-Ishai-Kushilevitz application to MPC).

After many years of research, in 2007 Desmedt-Pieprzyk-Steinfeld-Wang succeeded in making black-box “MPC” computations over non-Abelian groups. The motivation was purely theoretical. Today we will see an application of the situation in which:

the secret and shares belongs to a non-Abelian group, i.e.,Sn(or a subgroup ofSn, such asZn).

c

�Yvo Desmedt 6

2.

O

UR SETTING

: P

OST

S

NOWDEN ELECTIONS

Post Snowden: today most people understand that computers, laptops can be hacked and may have trapdoors, malware, etc.

Potential solutions:

•Halderman (2015) recommended to stop using Internet Voting.

•We believe we need to restart/encourage a line of research in which we wonder how to vote assuming that the device you use for voting

has been hacked.

Our model(high level): we assume we cannottrust:

•any single party,

•any single device, etc.

c

�Yvo Desmedt 7

4.

A

DVANTAGES

/

DISADVANTAGES OF CODE VOTING

Advantages of Code Voting:secure even if voter’s machine hacked.

Disadvantages:

•requires IACR to send random numbers by postal mail, and

•no collusion between postal system (or sender of envelopes) and the party receiving the vote.

•authorities do not like the system because it differs too much from what is used today!

c

�Yvo Desmedt 10

Ballot stuffing with Code Voting

c

�Yvo Desmedt and Stelios Erotokritou 11

4.

A

DVANTAGES

/

DISADVANTAGES OF CODE VOTING

Advantages of Code Voting:secure even if voter’s machine hacked.

Disadvantages:

•requires IACR to send random numbers by postal mail, and

•no collusion between postal system (or sender of envelopes) and the party receiving the vote.

•authorities do not like the system because it differs too much from what is used today!

c

�Yvo Desmedt 10

Ballot stuffing with Code Voting

c

�Yvo Desmedt and Stelios Erotokritou 11

3.

A

PIONEERING APPROACH

: C

HAUM

’

S

C

ODE

V

OTING

c

�Yvo Desmedt and Stelios Erotokritou 8

c

�Yvo Desmedt and Stelios Erotokritou 9

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

c

�Yvo Desmedt and Stelios Erotokritou 14

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

c

�Yvo Desmedt and Stelios Erotokritou 14

5.

O

UR SETTING

,

ASSUMPTIONS AND THEIR IMPACTS

Our setting:

1.Voter votes using an untrusted device

2.The voter has access to many communication devices/media (e.g., home PC, mobile, at work, in the library, postal)

3.Voter uses “human computations,”which we checked on reliability (see further).

4.Authoritiesuse untrusted computers, potentially with state sponsored malware.

c

�Yvo Desmedt 12

Our first model:

1.at mosttdevices/parties are infected.

2.our adversary is passive, curious, but not interested in: modifying the vote, in a DoS, etc. (see further)

Impact:

•Many cryptographic tools become useless, such as: AES, ElGamal, ZKIP, NIZK.

•So, we need to make a new MIX

c

�Yvo Desmedt 13

5.

O

UR SETTING

,

ASSUMPTIONS AND THEIR IMPACTS

Our setting:

1.Voter votes using an untrusted device

2.The voter has access to many communication devices/media (e.g., home PC, mobile, at work, in the library, postal)

3.Voter uses “human computations,”which we checked on reliability (see further).

4.Authoritiesuse untrusted computers, potentially with state sponsored malware.

c

�Yvo Desmedt 12

Our first model:

1.at mosttdevices/parties are infected.

2.our adversary is passive, curious, but not interested in: modifying the vote, in a DoS, etc. (see further)

Impact:

•Many cryptographic tools become useless, such as: AES, ElGamal, ZKIP, NIZK.

•So, we need to make a new MIX

c

�Yvo Desmedt 13

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

� �� �

φi

14

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

� �� �

φi 14

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

� �� �

φi

14

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

� �� �

φi

14

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

c

�Yvo Desmedt and Stelios Erotokritou 14

6.

T

HE VOTING

:

PASSIVE ADVERSARY ONLY

A user friendly approach: (multi-seat, not “code-voting”,t= 1)

c

�Yvo Desmedt and Stelios Erotokritou 14

Details:

We asked 100 participants to do several tests (their ages did not

surpass 65).

Asking to add 5 shares of 4 digitsmod10, 95% of the people computed the correct result, using the above visual tool to avoid

confusion.

However, when using the permutation based addition, 99% of the

people computed the correct result.

A common comment from the participants was that the permutation

basedmod10addition was extremely easy - whereas the other experiment was rather challenging for some people.

c

�Yvo Desmedt 17

8.

H

IGH LEVEL DESCRIPTION

Background: secret shares

Example: 2-out-of-2:

Goal:Give binary secretsto 2 parties, Alice and Bob.

How:Flip a coin. Give the result,s1, to Alice.

Give Bob:s⊕s1.

Can begeneralizedto:

•work over any finite group,

•the case we donottrusttinsiders. Just lets=s₁◦s₂◦ · · · ◦st+1.

c

�Yvo Desmedt 18

In the single-seat election (mix friendly), we use code-voting (t= 1)

We regard the Abelian groupZ10(+)as a subgroup ofS10and

replace the above “shares” by e.g.,

Put this edge against Arrow Sheet 2 Put this edge

against "Trace the Line" edge

Sheet 1 Sheet 2

Put against "Secret Bullets" Put against

Sheet 1

These corresponding to an addition plus 4mod10and plus 3

mod10respectively. We assume there are 10 candidates.

15

7.

S

OME USABILITY TESTS

(SCN 2012)

How good are users able to add strings of numbers, eachmod10? Our test show only 95% get this correct, even when helping users, as following:

2597 Your Secret is: Please re-write your secret:

2 5 9 7

+

+

+

+

7 2 9 1 1 6 5 8 9 2 0 2 7 4 8 4 8 1 7 2 1 8 2 4 2 9 5 0 8 7 2 6 2 4 1 7 1 9 7 8 1 7

2 9

1 5

3 2

Share 1 Share 2 Share 3 Share 4 Share 5

16

In the single-seat election (mix friendly), we use code-voting (t= 1)

We regard the Abelian groupZ10(+)as a subgroup ofS10and

replace the above “shares” by e.g.,

Put this edge against Arrow Sheet 2 Put this edge

against "Trace the Line" edge

Sheet 1 Sheet 2

Put against "Secret Bullets" Put against

Sheet 1

These corresponding to an addition plus 4mod10and plus 3

mod10respectively. We assume there are 10 candidates.

15

7.

S

OME USABILITY TESTS

(SCN 2012)

How good are users able to add strings of numbers, eachmod10? Our test show only 95% get this correct, even when helping users, as following:

2597 Your Secret is: Please re-write your secret:

2 5 9 7

+

+

+

+

7 2 9 1 1 6 5 8 9 2 0 2 7 4 8 4 8 1 7 2 1 8 2 4 2 9 5 0 8 7 2 6 2 4 1 7 1 9 7 8 1 7

2 9

1 5

3 2

Share 1 Share 2 Share 3 Share 4 Share 5

16

High level protocol description:

1.We use aCode Generation Entity(CGE), which will in the pre-voting stage chooseinitialone-time pad (informally,πi) for each

voter.

2.Our MIX network uses layers, each layer having at leastt+ 1

shares.

3.The CGE sends shares (t+ 1) of theseπito the MIX servers in the

first layer.

4.The MIX network anonymizes and modifies the shares ofπi. The

permutations used are the same for all the shares of the same value. For this, each layer had aleaderthat remembers the permutation used and the modifications done at that layer.

c

�Yvo Desmedt 19

5.Each server in the last layer of the MIX sends a share to each voter (communication paths used by different servers are vertex disjoint).

6.The voter combines the shares (see above) and votes.

7.The voter sends the “encrypted” vote back to the leader of the last layer of the MIX network.

8.Starting with the leader of the last layer, all permutations and modifications done at that layer are undone.

9.The leader of the first layer of the MIX sends the almost-unencrypted vote to the CGI.

10.The CGI uses the inverse of its one-time pad.

c

�Yvo Desmedt 20

High level protocol description:

1.We use aCode Generation Entity(CGE), which will in the pre-voting stage chooseinitialone-time pad (informally,πi) for each

voter.

2.Our MIX network uses layers, each layer having at leastt+ 1

shares.

3.The CGE sends shares (t+ 1) of theseπito the MIX servers in the

first layer.

4.The MIX network anonymizes and modifies the shares ofπi. The

permutations used are the same for all the shares of the same value. For this, each layer had aleaderthat remembers the permutation used and the modifications done at that layer.

c

�Yvo Desmedt 19

5.Each server in the last layer of the MIX sends a share to each voter (communication paths used by different servers are vertex disjoint).

6.The voter combines the shares (see above) and votes.

7.The voter sends the “encrypted” vote back to the leader of the last layer of the MIX network.

8.Starting with the leader of the last layer, all permutations and modifications done at that layer are undone.

9.The leader of the first layer of the MIX sends the almost-unencrypted vote to the CGI.

10.The CGI uses the inverse of its one-time pad.

c

�Yvo Desmedt 20

Details:

We asked 100 participants to do several tests (their ages did not

surpass 65).

Asking to add 5 shares of 4 digitsmod10, 95% of the people computed the correct result, using the above visual tool to avoid

confusion.

However, when using the permutation based addition, 99% of the

people computed the correct result.

A common comment from the participants was that the permutation

basedmod10addition was extremely easy - whereas the other experiment was rather challenging for some people.

c

�Yvo Desmedt 17

8.

H

IGH LEVEL DESCRIPTION

Background: secret shares

Example: 2-out-of-2:

Goal:Give binary secretsto 2 parties, Alice and Bob.

How:Flip a coin. Give the result,s1, to Alice.

Give Bob:s⊕s1.

Can begeneralizedto:

•work over any finite group,

•the case we donottrusttinsiders. Just lets=s1◦s2◦ · · · ◦st+1.

c

�Yvo Desmedt 18

10.

T

HE MIXING FOR THE SINGLE

-

SEAT

MIX-

FRIENDLY CASE

We have several protocols, of which we describe the simplest.

In the simplest, we require that each server in layeriis physically different from each server in layerj(i�=j).

Note: Our MIX-friendly protocols can also be used in situations in which we have a single receiver (can be generalized) and multiple senders. The receiver should not learn who the sender is. For simplicity we focus on voting.

In below protocol we assume thatb=t+ 1. We denote the servers in layeriby a “block”Bi.

Protocol1. Prevotingprotocol

Step 1Letπ1

i be theithone-time pad (where1≤i≤v). The receiver

c

�Yvo Desmedt 23

(CGI) shares eachπ1

i intot+ 1sharesπi,j1 ∈F2l(where

1≤j≤t+ 1) and privately sendsπ1

i,jto the corresponding MIX

M IX1,jin blockB1.

Step 2Theleader_{ofB1(we callM IX1,1) informs all others MIX servers}

inB1how they have to permute thei-index of all aboveπi,j1. This permutation is defined byρ1∈RSv.

Step 3On theiindices all MIX servers inB1apply the permutationρ1. So,

π1

i,j:=π1ρ1(i),j.

Step 4Theleader_{ofB1choosest+ 1random bit string modifiers}

ω1

i,j∈RF2land privately sendsω1_i,jto parties inB1.

Step 5For each(i, j)thet+ 1valuesπ1

i,jare regarded as shares ofπ1i. Similarly, thet+ 1valuesω1

i,jare regarded as shares ofω1i.

c

�Yvo Desmedt 24

9.

D

ETAILS

:

TECHNICAL BACKGROUND

We primarily use (besides MIX and shares):

•Concepts fromsecure multiparty computation

Simplified goal: given shares ofsand shares ofuhow to make shares ofs∗u,withoutcomputingsandu.

•Desmedt-Kurosawa 2000 introduced:

Definition1. We say that(X,B)is an(n, b, t)-verifiers set system if: 1.|X|=n,

2.|Bi|=t+ 1fori= 1,2, . . . , b, and

3.for any subsetF⊂Xwith|F| ≤t, there exists aBi∈ B such thatF∩Bi=∅.

c

�Yvo Desmedt 21

Vertex disjoint paths: pathsp1andp2fromStoRare vertex disjoint

if the nodes on pathp1, and onp2, except forSandRare disjoint.

c

�Yvo Desmedt 22

9.

D

ETAILS

:

TECHNICAL BACKGROUND

We primarily use (besides MIX and shares):

•Concepts fromsecure multiparty computation

Simplified goal: given shares ofsand shares ofuhow to make shares ofs∗u,withoutcomputingsandu.

•Desmedt-Kurosawa 2000 introduced:

Definition1. We say that(X,B)is an(n, b, t)-verifiers set system if: 1.|X|=n,

2.|Bi|=t+ 1fori= 1,2, . . . , b, and

3.for any subsetF⊂Xwith|F| ≤t, there exists aBi∈ B such thatF∩Bi=∅.

c

�Yvo Desmedt 21

Vertex disjoint paths: pathsp1andp2fromStoRare vertex disjoint

if the nodes on pathp1, and onp2, except forSandRare disjoint.

c

�Yvo Desmedt 22